/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/number-of-big-islands
   @Language: C++
   @Datetime: 19-06-14 09:44
   */

class Solution {
	int bfs(vector<vector<bool> > &grid, int r, int c){
		int row=grid.size(), col=grid[0].size(), area=0;
		queue<pair<int,int> > q;
		for(q.push({r,c}); q.size(); q.pop()){
			const int i=q.front().first, j=q.front().second;
			if(i<0 || i>=row || j<0 || j>=col) continue;
			if(!grid[i][j]) continue;
			++area;
			grid[i][j]=false;
			q.push({i+1,j});
			q.push({i-1,j});
			q.push({i,j+1});
			q.push({i,j-1});
		}
		return area;
	}
public:
	/**
	 * @param grid: a 2d boolean array
	 * @param k: an integer
	 * @return: the number of Islands
	 */
	int numsofIsland(vector<vector<bool> > &grid, int k) {
		// Write your code here
		int cnt=0;
		for(int i=0; i<grid.size(); ++i)
			for(int j=0; j<grid[i].size(); ++j)
				if(grid[i][j] && bfs(grid,i,j)>=k) ++cnt;
		return cnt;
	}
};
